package org.usmile.algorithms.learn.trie;

import java.util.ArrayList;
import java.util.List;

public class ArrayTrie {
    private final Node root;

    public ArrayTrie() {
        this.root = new Node('/');
    }

    private static class Node {
        private final Character c;

        private final List<Node> children;

        boolean isWord;

        public Node(Character c) {
            this.c = c;
            this.children = new ArrayList<>();
            this.isWord = false;
        }

        public int childrenCharIndex(Character c) {
            for (int i = 0; i < children.size(); i++) {
                if (children.get(i).c == c) {
                    return i;
                }
            }

            return -1;
        }
    }

    public void add(String word) {
        Node curr = root;

        for (Character c : word.toCharArray()) {
            int index = curr.childrenCharIndex(c);
            if (index == -1) {
                curr.children.add(new Node(c));
                index = curr.children.size() - 1;
            }

            curr = curr.children.get(index);
        }

        curr.isWord = true;
    }


    public boolean contains(String word) {
        Node curr = root;
        for (Character c : word.toCharArray()) {
            int index = curr.childrenCharIndex(c);
            if (index == -1) {
                return false;
            }
            curr = curr.children.get(index);
        }

        return curr.isWord;
    }

    public static void main(String[] args) {
        ArrayTrie arrayTrie = new ArrayTrie();
        arrayTrie.add("Hello");
        arrayTrie.add("World");

        System.out.println(arrayTrie.contains("Hello"));
        System.out.println(arrayTrie.contains("xx"));
    }
}
